﻿#include<iostream>
using namespace std;
const int N = 10010, M = 100010;

int n, m;
char p[N], s[M]; //S[]主串,p[]子串
int ne[N];////next[i]=j:前i个数前缀和后缀匹配j个

int main()
{
    cin >> n >> p + 1 >> m >> s + 1;//数组的数组名是数组的首地址，也就是下标为0的位置，+1就从下标为1的位置开始
    //求next的过程，next数组的求法是通过模板串自己与自己进行匹配操作得出来的
    for (int i = 2, j = 0; i <= n; i++)//只有字符串长度大于1的时候，才会存在非平凡前后缀。next[1]的值固定是0
    {
        while (j && p[i] != p[j + 1])    j = ne[j];//模式串之间的比较，不匹配
        if (p[i] == p[j + 1])    j++;//匹配
        ne[i] = j;
    }
    //kmp匹配
    for (int i = 1, j = 0; i <= m; i++)//i<=m小于模式串的长度
    {
        while (j && s[i] != p[j + 1])    j = ne[j];//主串和子串不匹配时，子串下标回到ne位置
        //当主串和子串永不匹配时，模式串会一直ne[]往前，直到j=0
        //while(j):j退回到起点
        if (s[i] == p[j + 1])    j++; //匹配，往后走
        if (j == n)//n是模式串的长度
        {
            //得到kmp子串，输出主串在所有匹配位置的起始下标
            printf("%d ", i - n);
            j = ne[j];//继续匹配下一个子串,//不是输出第一个匹配的，而是所有的
            //j=1?从头开始匹配？
        }
    }
}

/*
*总结
1.next[]也是找子串的一个过程,非常有意思的说法是:
求next数组时：对于每个i：“j走到哪了呀？我用数组记录一下你的位置” ne[i] = j;
匹配时：对于每个i：“到终点和我说声，匹配完我输出一下，没事别叫我。”
2.当j=n，匹配成功，输出并且j = ne[j]继续匹配下一个子串
*/
